짝지어 제거하기

📔 문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

📓 제약 조건

문자열의 길이 : 1,000,000이하의 자연수
문자열은 모두 소문자로 이루어져 있습니다.

📓 입출력의 예

❗ 1번째

먼저 이 경우에는 간단하게 스택을 받을때 스택에 담겨진 글자가있고 스택의 마지막과 현재 들어오는 글자가 같은경우에 스택에서 pop()해버리고 혹은 스택이 비어있거나 스택의 마지막과 다를경우 스택에 글자를 추가해주면 될거같다.

그후에는 스택의 길이가 0일경우에는 1을 리턴해주고 스택의 길이가 0이 아닐경우에 0을 리턴 해주겠다.

✅ 실행 코드

function solution(s){
    const stack = []
    let last
    for(const c of s){
        if(stack.length && stack[stack.length - 1] === c) {
            stack.pop()
        }else{
            stack.push(c)
        }           
    }
    if(stack.length === 0){
        return 1              
    }else{
        return 0
    }
}

📚 문제 느낀점

요구하는 제약조건에서 문자열의 길이가 100만까지 된다는건 N의 제곱으로 풀었을때는 1조가 넘어가므로 아마 풀 수 없어질것이다 즉 다른 방법으로 풀어야한다는 것이고 비교적 스택의 원리만 알면 금방 풀 수 있는 문제같다.

© 문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/12973